#include <bits/stdc++.h>
using namespace std;

template <typename T>
struct AVLNode {
	T key;
	int bf;
    struct AVLNode* LChild;
    struct AVLNode* RChild;
		AVLNode() {
		bf = 0;
		this->LChild = nullptr;
		this->RChild = nullptr;
	}
    AVLNode(T temp) : key(temp), bf(0),LChild(nullptr), RChild(nullptr){}
};

class AVLTree {
	typedef pair<string, string> word;
	typedef AVLNode<word> AVLNode, *BiTree;

    private:
        BiTree rt = nullptr;
	public:
		AVLTree(){}

		~AVLTree(){}

        //获取根节点
        BiTree getRt(){
            return this->rt;
        }

        //获取英文单词
		string getKey(AVLNode *w) {
			return w->key.first;
		}

        //获取中文翻译
		string getValue(AVLNode *w) {
			return w->key.second;
		}
		
        //获取平衡因子
		int getBf(AVLNode *w) {
			return w->bf;
		}

        //新建节点
        BiTree NewNode(string key,string value){
            BiTree w = new AVLNode(make_pair(key,value));
            return w;
        }

        //中序遍历
        void show(){
            showInfo(rt);
        }

        void showInfo(BiTree rt){
            if(!rt){
                return ;
            }
            showInfo(rt->LChild);
            cout << getKey(rt) << ' ' << getValue(rt) << ' ';
            showInfo(rt->RChild);
        }

        //右旋最小不平衡树
		void R_Rotate(BiTree *w) {
			//建立一个临时的节点指向当前节点的左孩子
			BiTree L;
			L = (*w)->LChild;
			//将当前节点的左节点指向临时节点的右孩子
			(*w)->LChild = L->RChild;
			//让临时节点指向当前节点完成右旋
			L->RChild = (*w);
			//w指向新节点
			*w = L;
		}

        //左旋最小不平衡树
		void L_Rotate(BiTree *w){
			//建立一个临时的节点指向当前节点的右孩子
			BiTree R;
			R = (*w)->RChild;
			//将当前节点的右孩子指向临时节点的左孩子
			(*w)->RChild = R->LChild;
			//让临时节点指向当前节点完成左旋
			R->LChild = (*w);
			//w指向新节点
            *w = R; 
		}

        //对左侧不平衡树进行调整
		void LeftBalance(BiTree *w) {
			BiTree L,Lr;
            //L指向w节点左孩子
			L = (*w)->LChild; 
            //判断左孩子的平衡因子选择相应的子树调整方式
			if (getBf(L) == 1) {
                //左孩子与w节点平衡因子相同
				(*w)->bf = L->bf = 0;
                //简单右旋即可平衡
				R_Rotate(w); 
			}else{
                //
                Lr = L->RChild;
                //调整平衡后的平衡因子
                if(getBf(Lr) == 1){
                    (*w)->bf = -1;
                    L->bf = 0;
                }else if(getBf(Lr) == 0){
                    (*w)->bf = L->bf = 0;
                }else if(getBf(Lr) == -1){
                    (*w)->bf = 0;
                    L->bf = 1;
                }
                Lr->bf = 0;
                //对子树进行平衡处理,树的形状不唯一，但依然保持有序，
                //仅对平衡因子进行修改目的是在左平衡时进行统一的变换
                //将左子树进行左旋操作
                L_Rotate(&(*w)->LChild);
                R_Rotate(w);
            }
		}

        //右侧平衡与左侧相同原理
        //参数稍有不同，不做过多的赘述
        void RightBalance(BiTree *w){
            BiTree R,Rl;
            R = (*w)->RChild;
            if(R->bf == -1){
                (*w)->bf = R->bf = 0;
                L_Rotate(w);
            }else{
                Rl = R->LChild;
                if(Rl->bf == -1){
                    (*w)->bf = 1;
                    R->bf = 0;
                }else if(Rl->bf == 0){
                    (*w)->bf = R->bf = 0;
                }else if(Rl->bf == 1){
                    (*w)->bf = 0;
                    R->bf = -1;
                }
                Rl->bf = 0;
                R_Rotate(&(*w)->RChild);
                L_Rotate(w);
            }
        }
        bool insertNode(word w){
            bool taller;
            bool ok;
            insertNode(&rt,w.first,w.second,&taller,&ok);
            return ok;
        }

        //插入节点
        void insertNode(BiTree *w,string key,string value,bool *taller,bool *ok){//taller是为了判断子树的高度是否发生了变换
            if(!(*w)){//如果节点为空则插入节点，高度增加
                (*w) = NewNode(key,value);
                *taller = true;
                *ok = true;
                return ;
            }else{
                if(key == getKey(*w)){//如果节点已经存在，则返回
                    *taller = false;
                    *ok = false;
                    return ;
                }
                if(key < getKey(*w)){//向左子树遍历
                    insertNode(&(*w)->LChild,key,value,taller,ok);
                    if(*taller){//如果高度发生变化则进行平衡处理
                        if((*w)->bf == 1){//根节点原平衡因子若为1则需要进行左侧平衡处理
                            LeftBalance(w);
                            *taller = false;
                        }else if((*w)->bf == 0){//根节点原平衡因子为0高度增加但不破环平衡向上回溯
                            (*w)->bf = 1;
                            *taller = true;
                        }else{//根节点原平衡因子为-1高度不变，平衡未打破
                            (*w)->bf = 0;
                            *taller = false;
                        }
                    }
                }else{//向右子树遍历，原理与左子树相同，不做过多赘述
                    insertNode(&(*w)->RChild,key,value,taller,ok);
                    if(*taller){
                        if((*w)->bf == 1){
                            (*w)->bf = 0;
                            *taller = false;
                        }else if((*w)->bf == 0){
                            (*w)->bf = -1;
                            *taller = true;
                        }else{
                            RightBalance(w);
                            *taller = false;
                        }
                    }
                }
            }
        }

        //节点查找,原理和树的输出相同
        string search(string key){
            return search(&rt,key);
        }

        string search(BiTree *w,string key){
            if(!(*w)){
                return "";
            }else{
                if(key == getKey(*w)){
                    return getValue(*w);
                }else if(key < getKey(*w)){
                    return search(&(*w)->LChild,key);
                }else{
                    return search(&(*w)->RChild,key);
                }
            }
        }

        //查找左子树的最大值，来替换删除节点
        BiTree getMaxValueNode(BiTree w){
            if(w->RChild){
                getMaxValueNode(w->RChild);
            }
            return w;
        }

        //删除节点
        bool deleteNode(string key){
            bool smaller;
            bool ok;
            deleteNode(&rt,key,&smaller,&ok);
            return ok;
        }

        void deleteNode(BiTree *w,string key,bool *smaller,bool *ok){//smaller用来记录删除节点后是否高度减少
            if(!(*w)){//未找到删除检节点
                *ok = false;
                return ;
            }else{
                if(key == getKey(*w)){
                    *ok = true;
                    if((*w)->LChild == nullptr || (*w)->RChild == nullptr){//该节点的孩子小于两个
                        *smaller = true;
                        BiTree q = nullptr;
                        if((*w)->LChild == nullptr){//只有右节点
                            q = (*w); (*w) = (*w)->RChild;//删除操作
                            delete q;
                        }else{
                            q = (*w); (*w) = (*w)->LChild;
                            delete q;
                        }
                    }else{//有两个子节点
                        BiTree t = getMaxValueNode((*w)->LChild);//向下寻找最大的子节点代替
                        //仅将数据交换
                        (*w)->key.first = t->key.first;
                        (*w)->key.second = t->key.second;
                        deleteNode(&(*w)->LChild,t->key.first,smaller,ok);//删除代替的节点
                    }
                }else if(key < getKey(*w)){//向左侧查找
                    deleteNode(&(*w)->LChild,key,smaller,ok);
                    if(*smaller){//左侧子树高度减少
                        if((*w)->bf == 1){//根节点原平衡因子为1平衡可能打破
                            (*w)->bf = 0;
                            *smaller = true;
                        }else if((*w) == 0){//根节点原平衡因子为0平衡未打破
                            (*w)->bf = -1;
                            *smaller = false;
                        }else if((*w)->bf == -1){//根节点原平衡因子为-1平衡打破，进行调整
                            (*w)->bf = 0;
                            *smaller = true;
                            RightBalance(w);
                        }
                    }
                }else if(key > getKey(*w)){//向右侧查找，原理和左侧相同，不做过多赘述
                    deleteNode(&(*w)->RChild,key,smaller,ok);
                    if(*smaller){
                        if((*w)->bf == 1){
                            (*w)->bf = 0;
                            *smaller = true;
                            LeftBalance(w);
                        }else if((*w)->bf == 0){
                            (*w)->bf = 1;
                            *smaller = false;
                        }else{
                            (*w)->bf = 0;
                            *smaller = true;
                        }
                    }
                }
            }
        }

        void load(string path){
                    ifstream file(path);
                    string s;
                    while(getline(file,s)){
                        int len = s.size();
                        string s1 = "",s2 = "";
                        int i;
                        for(i = 0; i < len && s[i] != ' '; ++i){
                            if(s[i] != ' '){
                                s1 += s[i];
                            }
                        }
                        for(i++;i < len; ++i){
                            s2 += s[i];
                        }
                        pair<string,string> p = make_pair(s1,s2);
                        this->insertNode(p);
                    }
                }
};
